Avoid quadratic slowdown in gtk_widget_add()
authorAlexander Larsson <alexl@redhat.com>
Thu, 4 Jun 2020 08:15:03 +0000 (10:15 +0200)
committerAlexander Larsson <alexl@redhat.com>
Thu, 4 Jun 2020 14:42:59 +0000 (16:42 +0200)
commitd3e0a1f68cd80019bdd39e566851371f8b03d1c1
treec460ca35dd156947daa97c1b71be6f4f5194142f
parent1998b673f4853ba1a5bc8218f673022dd61f1cdc
Avoid quadratic slowdown in gtk_widget_add()

If you add a widget to a parent, this will invalidate the css nodes
for parent/siblings. Afterwards, if the parent is mapped, we will
realize the new child. This calls gtk_widget_update_alpha() which
needs the css opacity, so it revalidates the css.

Thus, for each widget_add (while visible) will trigger a full
revalidation of each sibling. If you add N children to a parent that
leads to O(N^2) revalidations.

To demo this I changed gtk-demo to always double the count
(independent of the fps) and print the time it took. Here is the
results (after a bit):

Setting fishbowl count=256 took 3,4 msec
Setting fishbowl count=512 took 10,1 msec
Setting fishbowl count=1024 took 34,1 msec
Setting fishbowl count=2048 took 126,3 msec
Setting fishbowl count=4096 took 480,3 msec
Setting fishbowl count=8192 took 1892,7 msec
Setting fishbowl count=16384 took 7751,0 msec
Setting fishbowl count=32768 took 38097,7 msec
Setting fishbowl count=65536 took 191987,7 msec

To fix this we drop gtk_widget_update_alpha() and just
calculate it when needed (which is only in a single place).
It was really only necessary because we previously set
the alpha on the surface.

With this fix the above becomes:

Setting fishbowl count=256 took 1,0 msec
Setting fishbowl count=512 took 1,9 msec
Setting fishbowl count=1024 took 3,7 msec
Setting fishbowl count=2048 took 7,4 msec
Setting fishbowl count=4096 took 18,1 msec
Setting fishbowl count=8192 took 31,0 msec
Setting fishbowl count=16384 took 66,3 msec
Setting fishbowl count=32768 took 126,7 msec
Setting fishbowl count=65536 took 244,6 msec
Setting fishbowl count=131072 took 492,2 msec
Setting fishbowl count=262144 took 984,3 msec
gtk/gtkwidget.c
gtk/gtkwidgetprivate.h